# -*- coding: utf-8 -*-
"""
    Time    : 2020/12/30 9:26 下午
    Author  : Thinkgamer
    File    : add08-给定一个值找出其最大的前序序列.py
    Desc    : 快手面试
              前序序列的定义：比如 372 的最大前序序列为：327
"""


def previous_permutation(arr):
	# 如果arr的长度为1，直接返回
	if len(arr) == 1:
		return arr
	# 从右开始往左遍历，找到非升序的数字
	end = len(arr)-2
	while end > 0:
		if arr[end] < arr[end + 1]:
			end -= 1
		else:
			break
	# end == 0 表示arr是一个升序数组，无法找到其最大的前序序列
	if end == 0:
		return arr
	
	# 进行数据交换, 找到比 target 小的数中的最大值, 计作 min_v 放在end位，剩下的数字进行降序，放在end之后的位置
	target = arr[end]
	temp_arr = sorted(arr[end: len(arr)], key=(lambda k: k), reverse=True)
	min_v = 0
	min_index = 0
	for i in range(len(temp_arr)):
		if min_v < temp_arr[i] < target:
			min_v = temp_arr[i]
			min_index = i
	arr[end] = min_v
	for one in temp_arr[0:min_index] + temp_arr[min_index + 1:len(temp_arr)]:
		end += 1
		arr[end] = one
	return arr


arrs = [
	[4, 5, 2, 3, 6, 7],
	[3, 7, 2],
	[1, 2, 3]
]
for arr in arrs:
	result = previous_permutation(arr)
	print(result)
